package demo.practice.sort;

public class P31 {

    public static void main(String[] args) {
        P31 p31 = new P31();
        p31.nextPermutation(new int[]{2,3,1});
    }

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int max = nums.length - 1;
        boolean swaped = false;
        for (int i = max; i >= 0; i--) {
            if (i - 1 >= 0 && nums[i] > nums[i - 1]) {
                //swap(nums, max, i - 1);
                //123456 -> 123465  >   123546
                //首先是需要把更大的数往前面调,找到第一个  nums[i - 1]<nums[i]  前面比后面小的数
                //将 i - 1  位置上的数换成比现在大的数，但是最小的那个数
                int tmp=nums[i - 1];
                for(int j=max;j>=0;j--){
                    if(tmp< nums[j]){
                        swap(nums,j, i - 1);
                        break;
                    }
                }

                for(int si=i;si<=max;si++){
                    for(int sj=si+1;sj<=max;sj++){
                        if(nums[si]>nums[sj]){
                            swap(nums,si,sj);
                        }
                    }
                }
                swaped=true;
                break;
                //换完之后，保证这以为比原来大了，并且是最接近的更大，然后要保证i~max上的数字是最小的排列
            }
        }

        if (!swaped) {
            //倒序
            for (int j = 0; j < nums.length / 2; j++) {
                swap(nums, j, max - j);
            }
        }
    }


    public void swap(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }



}
